package com.licw.templates.SegmentTree;


/**
 * 支持区间更新
 */
public class SegmentTree1 {
    private final int[] sum;
    private final int[] lazy;
    private final int maxV;

    public SegmentTree1(int maxV) {
        this.maxV = maxV;
        // 设置为4 * n也行, 下面写法更节省内存
        int sz = 2 << (32 - Integer.numberOfLeadingZeros(maxV));
        this.sum = new int[sz];
        this.lazy = new int[sz];
    }

    /**
     * 注意下标从1开始， 出入初始值数组对应也应该是下标从1开始
     */
    public void build(int[] arr) {
        build(1, 1, maxV, arr);
    }

    public void build(int o, int l, int r, int[] arr) {
        if (l == r) {
            sum[o] = arr[l]; // 线段树记录[1, maxV]
            return;
        }
        int m = (r - l) / 2 + l;
        build(o * 2, l, m, arr);
        build(o * 2 + 1, m + 1, r, arr);
        pushUp(o);
    }

    /**
     * 区间更新，更新[ul, ur]的元素
     */
    public void update(int ul, int ur, int val) {
        this.update(1, 1, maxV, ul, ur, val);
    }

    /**
     * 查询[l, r]区间和
     */
    public int query(int ql, int qr) {
        return this.query(1, 1, maxV, ql, qr);
    }


    /**
     * @param o   当前节点
     * @param l   当前节点左边界
     * @param r   当前节点右边界
     * @param ul  更新区间左边界
     * @param ur  更新区间右边界
     * @param add 修改（增加）值
     */
    private void update(int o, int l, int r, int ul, int ur, int add) {
        if (l > ur || r < ul) return;

        if (ul <= l && ur >= r) {
            sum[o] += (r - l + 1) * add;
            lazy[o] += add; // 标记[ l,  r]的值增加val
            return;
        }
        // 需要查找孩子节点，要将lazy标记向下传递
        pushDown(o, l, r);
        int m = (r - l) / 2 + l;
        update(o * 2, l, m, ul, ur, add);
        update(o * 2 + 1, m + 1, r, ul, ur, add);
        pushUp(o);//向上更新
    }

    private void pushUp(int o) {
        sum[o] = sum[o * 2] + sum[o * 2 + 1];
    }

    /**
     * 将lazy下推
     */
    private void pushDown(int o, int l, int r) {
        if (l == r || lazy[o] == 0) return;
        // 更新左右孩子节点的值，为lazy标记×孩子节点表示的区间长度
        int m = (r - l) >> 1 + l;
        sum[o * 2] += (m - l + 1) * lazy[o];
        sum[o * 2 + 1] += (r - (m + 1) + 1) * lazy[o];
        // 将lazy标记向下传给左右孩子节点
        lazy[o * 2] += lazy[o];
        lazy[o * 2 + 1] += lazy[o];
        // 清除该节点的lazy标记，防止重复更新
        lazy[o] = 0;
    }

    /**
     * 查询区间[qL, qR] 的结果
     *
     * @param o  当前节点
     * @param l  当前节点左边界
     * @param r  当前节点右边界
     * @param qL 查询区间左边界
     * @param qR 查询区间右边界
     */
    private int query(int o, int l, int r, int qL, int qR) {
        // 如果没有交集
        if (l > qR || r < qL) return 0;

        // 如果节点区间位于查询区间之内，直接返回该区间的值
        if (qL <= l && qR >= r) {
            return sum[o];
        }
        int res = 0;
        pushDown(o, l, r);

        int m = (r - l) / 2 + l;
        res += query(o * 2, l, m, qL, qR);
        res += query(o * 2 + 1, m + 1, r, qL, qR);
        pushUp(o);
        return res;
    }

}